package Leetcode.贪心;

import java.util.Arrays;
import java.util.Comparator;

class Item {
    int weight;
    int value;

    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }

}

public class FractionalKnapsack {

    public static double getMaxValue(Item[] items, int capacity) {
        Arrays.sort(items, (i1, i2) -> (int) ((double)i2.value / i2.weight - (double)i1.value / i1.weight));

        double totalValue = 0.0;
        for (Item item : items) {
            if (capacity - item.weight >= 0) {
                capacity -= item.weight;
                totalValue += item.value;
            } else {
                totalValue += item.value * ((double) capacity / item.weight);
                break;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60), new Item(20, 100), new Item(30, 120)
        };
        int capacity = 50;

        double maxValue = getMaxValue(items, capacity);
        System.out.println("最大价值: " + maxValue);
    }
}
/*
#include <stdio.h>
#include <stdlib.h>

// 定义活动结构体
typedef struct Item {
    int weight;
    int value;
} Item;

// 比较函数，用于排序
int compareItems(const void *a, const void *b) {
    Item *itemA = (Item *)a;
    Item *itemB = (Item *)b;
    double valuePerWeightA = (double)itemA->value / itemA->weight;
    double valuePerWeightB = (double)itemB->value / itemB->weight;
    if (valuePerWeightB > valuePerWeightA) return 1;
    else if (valuePerWeightB < valuePerWeightA) return -1;
    else return 0;
}

// 获取最大价值
double getMaxValue(Item items[], int n, int capacity) {
    // 使用qsort进行排序
    qsort(items, n, sizeof(Item), compareItems);

    double totalValue = 0.0;
    for (int i = 0; i < n; i++) {
        if (capacity >= items[i].weight) {
            capacity -= items[i].weight;
            totalValue += items[i].value;
        } else {
            totalValue += items[i].value * ((double)capacity / items[i].weight);
            break;
        }
    }
    return totalValue;
}

int main() {
    Item items[] = {
        {10, 60}, {20, 100}, {30, 120}
    };
    int n = sizeof(items) / sizeof(items[0]);
    int capacity = 50;

    double maxValue = getMaxValue(items, n, capacity);
    printf("最大价值: %f\n", maxValue);

    return 0;
}

 */